package qjc.h_二叉树;

import com.二叉树.练习题.TreeNode;

public class h13_路径总和III {
    /**
     * 采用双重递归：
     * 1. 外层递归：遍历每个节点，将其作为路径的起点；
     * 2. 内层递归：从当前节点出发，计算所有向下路径中和等于目标值的路径数量。
     *
     * @param root
     * @param targetSum
     * @return
     */
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        int res = rootSum(root, targetSum);
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);
        return res;
    }

    private int rootSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        int k = 0;
        int val = root.val;
        if (val == targetSum) {
            k++;
        }
        k += rootSum(root.left, targetSum - val);
        k += rootSum(root.right, targetSum - val);
        return k;
    }
}
